/*
 * @lc app=leetcode.cn id=895 lang=typescript
 *
 * [895] 最大频率栈
 */

// @lc code=start
class FreqStack {
  // 数字的频率
  freq: Map<number, number>;
  // 不同的频率对应的栈
  stacks: Map<number, number[]>;
  // 最高频率
  maxFreq: number;
  constructor() {
    this.freq = new Map();
    this.stacks = new Map();
    this.maxFreq = 0;
  }

  push(val: number): void {
    // 增加val的频率
    this.freq.set(val, (this.freq.get(val) ?? 0) + 1);
    const freq = this.freq.get(val)!;
    // 如果当前频率没有栈，创建
    if (!this.stacks.has(freq)) {
      this.stacks.set(freq, []);
    }
    // 将val压入多对应频率的栈中
    this.stacks.get(freq)!.push(val);
    // 更新最高频率
    this.maxFreq = Math.max(this.maxFreq, freq);
  }

  pop(): number {
    const stack = this.stacks.get(this.maxFreq)!;
    // 将当前数字从最高频率栈中移除
    const val = stack.pop()!;
    // 减少当前数字的频率
    this.freq.set(val, this.freq.get(val)! - 1);
    // 如果最高频率栈中为空，最高频率减少
    if (this.stacks.get(this.maxFreq)?.length === 0) {
      this.maxFreq--;
    }
    return val;
  }
}

/**
 * Your FreqStack object will be instantiated and called as such:
 * var obj = new FreqStack()
 * obj.push(val)
 * var param_2 = obj.pop()
 */
// @lc code=end
